package Simple3;

import java.util.ArrayList;
import java.util.HashMap;

public class String_Problems {
	public String_Problems(){
		
	}
	
	/**
	 * Find the longest palindrome in a String s
	 * This is an O(N^2) solution with DP. 
	 * @param s
	 * @return
	 */
	public String getLong_Pa(String s){
		if(s==null || s.length()==0) return null;
		int start=0, end = 0;
		boolean[][] in = new boolean[s.length()][s.length()];
		for(int i=0;i<s.length();++i){
			for(int j=0;j<s.length()-i;++j){
				if(s.charAt(j)==s.charAt(j+i) && (i<2 || in[j+1][j+i-1])){
					in[j][j+i] = true;
					start = j;
					end = j+i;
				}
			}
		}
		
		return s.substring(start,end+1);
	}

	/**
	 * O(N) solution of find the longest palindrome in a Sting.
	 * @param s
	 * @return
	 */
	public String getLong_Pa_DP(String s){
		String t = transform(s);
		int[] p = new int[t.length()];
		int c = 0, end = 0; // center and end of current longest substring
		for(int i=1;i<t.length()-1;++i){
			if(end>i){
				p[i] = Math.min(p[c*2-i], (end-i));
			}
			while(t.charAt(i+p[i]+1)==t.charAt(i-p[i]-1)){
				p[i]++;
			}
			
			//if palindrome centered at i and expand past r,
			// adjust the center
			if(i+p[i]>end){
				c = i;
				end = i+p[i];
			}
		}
		//find the maximum length
		c=0;int r=0; // center and radius
		for(int i=0;i<p.length-1;++i){
			if(p[i]>r){
				c = i;
				r = p[i];
			}
		}
		return s.substring((c-r-1)/2, (c+r)/2);
	}
	
	/**
	 * Change "abba" to "^#a#b#b#a#$" to avoid odd and even problem
	 * @param s
	 * @return
	 */
	private String transform(String s){
		int n = s.length();
		if(n==0) return "^$";
		String ret = "^";
		for(int i=0;i<n;++i){
			ret += "#" + s.charAt(i);
		}
		ret +="#$";
		return ret;
	}

	
	/**
	 * Find the longest unrepeated substring in a string, like
	 * 		abcdeab should return abcde or cdeab
	 * @param s
	 * @return
	 */
	public String getLongest_unrepeat(String s){
		int maxLen = 0;
		int start = 0, end=0;
		int index1=0, index2=0;
		HashMap<Character, Integer> map = new HashMap<>();
		while(end<s.length()){
			char temp = s.charAt(end);
			if(map.containsKey(temp) && map.get(temp)>=start){
				if(end-start>maxLen){
					maxLen = end-start;
					index1 = start;
					index2 = end;
				}
				start = map.get(temp)+1;
			}
			map.put(temp, end++);
		}
		maxLen = Math.max(maxLen, end-start);
		return s.substring(index1,index2);
	}

	/**
	 * Find the longest repeated substring in a string.
	 * e.g. "abcdabc" will return abc
	 * @param s
	 * @return
	 */
	public String getLongest_repeat(String s){
		//TODO
		return null;
	}
	
	
	/**
	 * Find the common substring of two String.
	 * @param s1
	 * @param s2
	 * @return
	 */
	public String getCommon(String s1, String s2){
		//maxlen the length of common substring, 
		// maxindex is the start index of substring in s1
		int maxlen = 0, index = 0;
		
		//dp show the length of substring in common that end with i in s1
		// and end with j in s2
		int[][] dp = new int[s1.length()][s2.length()]; 
		for(int i=0;i<s1.length();++i){
			for(int j=0;j<s2.length();++j){
				if(s1.charAt(i)==s2.charAt(j)){
					if(i==0 || j==0){
						dp[i][j]=1;
					}
					else{
						dp[i][j] = dp[i-1][j-1]+1;
					}
				}
				if(dp[i][j]>maxlen){
					maxlen = dp[i][j];
					index = i-maxlen+1;
				}
			}
		}
		return s1.substring(index,index+maxlen);
	}
	
	/**
	 * Find the missing number of range. like "910111314" return "12"
	 * @param s
	 * @return
	 */
	public String findMissing(String s){
		//TODO 
		if(s==null || s.length()==0) return null;
		ArrayList<Integer> ret = new ArrayList<>();
		helper(s, null, ret);
		return String.valueOf(ret.get(0));
	}
	
	private void helper(String s, Integer preNum,ArrayList<Integer> ret){
		if(s==null || s.length()==0){
			ret.add(preNum+1);
			return;
		}
		int num1=0;
		for(int i=0;i<s.length();++i){
			num1 = num1*10 + s.charAt(i)-'0';
			if(preNum==null || num1==preNum+1){
				helper(s.substring(i+1), num1, ret);
			}
			else if(num1==preNum+2){
				ret.add(preNum+1);
				return;
			}
			else if(num1>preNum+2){
				//need to break, e.g when we check 91012
				// pre=9, num1=10, no need to check num1=101
				return;
			}
		}
	}
	
	
	/**
	 * Decompress a string like g00x3gle-->g0gle
	 * 							3xa2xb-->aaabb
	 * 							0010xa--->00aaaaaaaaaa
	 * @param s
	 * @return
	 */
	public String decompress(String s){
		if(s==null || s.length()==0) return "";
		ArrayList<String> ret = new ArrayList<>();
		helper(s, new StringBuilder(), ret);
		return ret.get(0);
	}
	
	private void helper(String s, StringBuilder sb, ArrayList<String> ret){
		if(s.length()==0){
			ret.add(sb.toString());
			return;
		}
		//index_num----> the index of starter of number
		//num----> the number before x
		//pow----> the pow of 10
		int i=0,index_num=0,pow=1,num=0;
		while(i<s.length()){
			if(s.charAt(i)=='x')
				break;
			i++;
		}
		if(i==0){		//the first character is x
			sb.append(s.charAt(i));
			helper(s.substring(1), sb, ret);
		}
		else if(i==s.length() || i==s.length()-1){	//here is no "x" or x is the last
			sb.append(s);
			helper("", sb, ret);
		}
		else{		//we have a common case like "aa2xb"-->"aabb"
			int start_zero = 0;
			index_num=i-1;
			//get the number before "x"
			while(index_num>=0){
				char c = s.charAt(index_num);
				if(c>='0' && c<='9'){
					num += (c-'0')*pow;
					pow *= 10;
				}
				else
					break;
				index_num--;
			}
			//add substring before number
			sb.append(s.substring(0,index_num+1));
			
			//add 0s, like 010xa--->0aaaaaaaaaa
			for(int k=index_num+1;k<i-1;k++){
				if(s.charAt(k)=='0')
					start_zero++;
				else
					break;
			}
			for(int j=0;j<start_zero;++j)
				sb.append('0');
			
			//add numbers of the specific character after "x"
			for(int j=0;j<num;++j)
				sb.append(s.charAt(i+1));
			helper(s.substring(i+2), sb, ret);
		}
	}
	
	/**
	 * Compress a string like google-->go2gle
	 * @param s
	 * @return
	 */
	public String compress(String s){
		StringBuffer sb = new StringBuffer();
		int i=0;
		while(i<s.length()){
			int count=0;
			char c = s.charAt(i);
			while(i<s.length() && s.charAt(i)==c){
				count++;
				i++;
			}
			if(count==1)
				sb.append(c);
			else{
				sb.append(c);
				sb.append(count);
			}
		}
		return sb.toString();
	}
	
	/**
	 * You are given two Strings lets say "S" which consist Upper Case alphabets 
	 * and '?' character only and p. 
	 * You are required to replace '?' with some alphabet so that 
	 * resulting string have maximum number of "p" in it. 
	 * You can replace '?' with any alphabet. 
	
		2. Replace '?' such that it should be lexicographically sorted. 
		Example 
		S="ABAAMA????MAZON????????" 
		p="AMAZON" 
		The final string S = "ABAAMAZONAMAZONAAAMAZON" 

		S="?????" 
		p="ABCD" 
		Final Result="AABCD" 
	 * @param args
	 */
	public String combineString(String s, String p){
		return null;
	}
	
	public static void main(String[] args) {
		
		String_Problems test = new String_Problems();
		String testString = "babcbabcbaccba";
//		System.out.println(test.getLong_Pa(testString));
//		System.out.println(test.getLong_Pa_DP(testString));
//		System.out.println(test.getCommon("cdabba", "cdeeabbacd"));
//		System.out.println(test.getLongest_unrepeat("abcc"));
//		System.out.println(test.compress("aaaaaaaaaaabb"));
//		System.out.println(test.decompress("0010xax1x"));
//		System.out.println(test.findMissing("99100101103"));
	}

}
